home *** CD-ROM | disk | FTP | other *** search
/ Pascal Super Library / Pascal Super Library (CW International)(1997).bin / DELPHI32 / MATH / PI / README.TXT < prev   
Text File  |  1996-06-17  |  6KB  |  151 lines
  1. PI Calculator version 1.0
  2. =========================
  3.  
  4. I was cleaning out the piles of paper lying everywhere the other day when I
  5. came across some work I did when I was a Uni student. It's been a while since
  6. I last worked on this but I thought it would be interesting to see how my new
  7. computer did at calculating PI compared to the VAX we used way back in 1986.
  8.  
  9. At the time it was an interesting exercise in writing code in C. Now ten years
  10. on I find I'm back to writing code in Pascal. When I originally wrote the
  11. programs there were many problems that had to be overcome. The university
  12. computer was running Unix and, while originally designed for up to 30 users,
  13. could have almost 200 running on it at a time. Response times were hopeless of
  14. course. Consequently I used batch jobs to do the processing. Batch processes
  15. where limited to 4 hours before they were terminated. However I discovered that
  16. while running my calculations the system was so busy that the batch timer
  17. didn't kick in until 4 hours 30 minutes. Hence as I increased performance I
  18. would have to guess how many digits I would be able to get in a run. After a
  19. while I set it up so that there was a series of batch jobs, each one calling
  20. the next in series in order to get the three arctan's and then one more to do
  21. the final summation. Using this method I was able to calculate 36,000 digits
  22. in a run that took about 11 hours to run.
  23.  
  24. Anyway, hope you find this of as much interest as I did. If you use or modify
  25. the code remember you need to give me credit for it. Other than that it's all
  26. yours. Enjoy.
  27.  
  28. Jason Andre
  29.  
  30.  
  31. The Formula
  32. ===========
  33.  
  34. This information comes from two books. My notes are a bit scratchy and faded
  35. now, but, at a guess,
  36.  
  37. 1) The One Million Digits of PI, Guilloud and Bouyer, 1960's?
  38. 2) The Computer Age?
  39.  
  40. {I'll check this out one day, or if someone could send me the info then great.}
  41.  
  42. The value of PI was first calculated in 1949 on the ENIAC computer using the
  43. formula,
  44.  
  45.              pi = 16 arctan(1/5) - 4 arctan(1/239)
  46.  
  47. which is known as machin's Formula. It calculated 2037 digits in 70 hours.
  48.  
  49. The formula I used was,
  50.  
  51.              pi = 48 arctan(1/18) + 32 arctan(1/57) - 20 arctan(1/239)
  52.  
  53. this was used on a 7600 Control Data computer to generate 1,000,000 digits in
  54. 23 hours and 18 minutes in 196? (I'd assume 1968 or 1969).
  55.  
  56. I presume that calculating the two arctan's, 1/18 and 1/57, is preferred as
  57. the partial sums will reduce much quicker than for the arctan 1/5.
  58.  
  59.  
  60. The Method for calculating the ArcTan
  61. =====================================
  62.  
  63. The arctan is calculated as a series of continuously reducing partial sums,
  64.  
  65.       ArcTan 1/K = SUM(p = 0 to infinity) of (-1)^p/(2p + 1)K^(2p+1)
  66.  
  67. The partial sums can be expressed as,
  68.  
  69.       Vn+1 = -(2n + 1)/(2n + 3) * 1/K^2 * Vn
  70.  
  71. I use the variables vm for Vn and vn for Vn+1, confusing huh! Still the
  72. algorithm is quite simple. The first value of course is for p=0 and this
  73. reduces to v0 = 1/K which is what I set both vm and vn to at the start. Then
  74. I keep reducing vn and adding or subtracting it from vm which is the current
  75. sum.
  76.  
  77.  
  78. Obvious improvements that can be made to the algorithm
  79. ======================================================
  80.  
  81. 1) The most obvious one, and I will get around to it one day, is to change the
  82. array's Vn and Vm, into arrays of integers. Then each array element can store
  83. more digits which will immediately improve the performance of the calculation.
  84. The change which I have made, from storing single digits, 0..9, in the array,
  85. to storing 2 digits, 0..99, pretty well doubled the performance of the
  86. algorithm. A similar improvement could be made by switching to an integer with
  87. 4 digits, 0..9999. The only thing to watch here is that none of the
  88. multiplcations or divides could result in numbers greater than MaxInt.
  89.  
  90. 2) Another thing that might be worth considering once the array has been
  91. converted to integers would be to allow up to 8 digits per element but do all
  92. calulations with 64 bit integers. I believe 386's and up do support this, they
  93. use the eax and edx registers, but I don't think Delphi does. The question of
  94. course would be whether or not the extra work handling 64 bit integers would
  95. gain you much speed, I assume it would.
  96.  
  97. 3) And of course, the most obvious change, try out Delphi's speed optimizations,
  98. I haven't gotten around to looking at these.
  99.  
  100.  
  101. The Results
  102. ===========
  103.  
  104. Arctan      Vax 11/780(?)      PC          7600 CDC
  105.  
  106. Digits        36,000         50,000       1,000,000
  107.  
  108. 1/18           4h20m          9m33s           9h53m
  109. 1/57           3h20m          6m49s           7h04m
  110. 1/239          2h20m          5m03s           5h14m
  111.  
  112. PI             1h                             1h07m
  113.  
  114. Total       ~ 11h            21m25s           23h18m
  115.  
  116. The ZIP supplied with this includes the partial sums and PI for 5000 digits.
  117. This took about 13 seconds on my PC.
  118.  
  119.  
  120. My PC
  121. =====
  122.  
  123. P166 w 32MB DRAM
  124. Matrox Millenium 2Mb WRAM
  125. 512KB Synchronous SRAM
  126. Running Windows 95
  127.  
  128. I assume that once you go beyond about 100,000 digits the data arrays would
  129. not remain cached and so the processing would slow down. (Although once the
  130. partial sum reduces it will all run in the cache again).
  131.  
  132.  
  133. Self Promotion
  134. ==============
  135.  
  136. B.Sc. and B.E. (Elec) from Sydney University
  137. 9 years programming experience, 7 of them as a Contract Programmer
  138. Languages:
  139.   Assembler (rusty)
  140.   C, C++
  141.   Pascal
  142. Major Projects worked on in the past:
  143.   Delphi Framework, used to hide complexities of a lower level interface (now)
  144.   Point of Sale system (now)
  145.   Various Terminal Emulations and Transports (1994-now)
  146.   Imaging System, Device Level stuff and Image manipulation (1991-1993)
  147.   Multi-User DOS Kernel (1990)
  148.   386 BIOS, Keyboard with a Mouse attached, Device Drivers etc (1989)
  149.   TSR Messaging System for use on Novell Networks (1987, 1988)
  150.  
  151.